package com.algrithom.math;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang3.StringUtils;

/**
 * 螺旋矩阵 54
 */
class Solution6 {
    
    public static void main(String[] args){
        int[][] matrics = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(StringUtils.join(spiralOrder1(matrics)));
    }
    
    /**
     * 螺旋矩阵
     *
     * @param matrix 矩阵
     * @return 列表
     */
    public static List<Integer> spiralOrder1(int[][] matrix){
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0) {
            return ans;
        }
        int row = matrix.length, col = matrix[0].length;
        boolean[][] seen = new boolean[row][col];
        int[] dr = {0,1,0,-1};
        int[] dc = {1,0,-1,0};
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < row * col; i++) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int cr = r + dr[di];
            int cc = c + dc[di];
            if (0 <= cr && cr < row && 0 <= cc && cc < col && !seen[cr][cc]) {
                r = cr;
                c = cc;
            } else {
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;
    }
    
    /**
     * 螺旋矩阵
     *
     * @param matrix 矩阵
     * @return 列表
     */
    public static List<Integer> spiralOrder2(int[][] matrix){
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0)
            return ans;
        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int c = c1; c <= c2; c++) {
                ans.add(matrix[r1][c]);
            }
            for (int r = r1 + 1; r <= r2; r++) {
                ans.add(matrix[r][c2]);
            }
            if (r1 < r2 && c1 < c2) {
                for (int c = c2 - 1; c > c1; c--) {
                    ans.add(matrix[r2][c]);
                }
                for (int r = r2; r > r1; r--) {
                    ans.add(matrix[r][c1]);
                }
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ans;
    }
    
    /**
     * 螺旋矩阵2
     *
     * @param n 输入
     * @return 螺旋矩阵
     */
    private static int[][] generateMatrix2(int n){
        int l = 0;
        int r = n - 1;
        int t = 0;
        int b = n - 1;
        int[][] mat = new int[n][n];
        int num = 1, tar = n * n;
        while (num <= tar) {
            for (int i = l; i <= r; i++) {
                mat[t][i] = num++;
            }
            t++;
            for (int i = t; i <= b; i++) {
                mat[i][r] = num++;
            }
            r--;
            for (int i = r; i >= l; i--) {
                mat[b][i] = num++;
            }
            b--;
            for (int i = b; i >= t; i--) {
                mat[i][l] = num++;
            }
            l++;
        }
        return mat;
    }
    
    int[] nxtCell(int rIx,int cIx,int r0,int c0){
        //若為出發點，直接回傳右側點
        if (rIx == r0 && cIx == c0) {
            return new int[]{r0,c0 + 1};
        }
        int dst0 = Math.max(Math.abs(rIx - r0),Math.abs(cIx - c0));
        if (cIx > c0 && dst0 == cIx - c0 && rIx - r0 != dst0 && r0 - rIx != dst0) {
            return new int[]{rIx + 1,cIx};
        } else if (rIx > r0 && dst0 == rIx - r0 && c0 - cIx != dst0) {
            return new int[]{rIx,cIx - 1};
        } else if (cIx < c0 && dst0 == c0 - cIx && r0 - rIx != dst0) {
            return new int[]{rIx - 1,cIx};
        } else if (rIx < r0 && dst0 == r0 - rIx) {
            return new int[]{rIx,cIx + 1};
        }
        return null;
    }
    
    public int[][] spiralMatrix3(int R,int C,int r0,int c0){
        int ttl = R * C;
        List<int[]> ans = new ArrayList<>();
        int[] cur = new int[]{r0,c0};
        ans.add(cur);
        while (ans.size() < ttl) {
            cur = nxtCell(cur[0],cur[1],r0,c0);
            if (0 <= cur[0] && cur[0] < R && 0 <= cur[1] && cur[1] < C) {
                ans.add(cur);
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}
